package com.zy.algorithm.v2;

import com.zy.algorithm.v2.bean.CountSimpleNode;
import com.zy.algorithm.v2.bean.QuickSimpleNode;
import com.zy.algorithm.v2.bean.SimpleNode;
import com.zy.utils.DataBuildUtils;
import com.zy.zlog.ZLog;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SortUtilsV2 {

    public static List<SimpleNode> bubbleSortAnimationV2(int size, int range) {
        List<Integer> sorted = new ArrayList<>();
        return bubbleSortAnimationV2(sorted, DataBuildUtils.getRandomSortArray(size, range));
    }

    //冒泡排序
    public static List<SimpleNode> bubbleSortAnimationV2(List<Integer> sorted, int[] array) {
        List<SimpleNode> stepList = new ArrayList<>();

        for (int i = 0; i < array.length - 1; i++) {
            boolean exchange = false;
            for (int j = 0; j < array.length - 1 - i; j++) {

                int firstOpV = array[j];
                int secondOpV = array[j + 1];

                boolean result = firstOpV > secondOpV;

                if (result) {
                    array[j] = secondOpV;
                    array[j + 1] = firstOpV;
                    exchange = true;


                    SimpleNode simpleNode = new SimpleNode();
                    simpleNode.setDes("数组大小:" + array.length + " 已排序:" + i);
                    simpleNode.setStepEnd(Arrays.copyOf(array, array.length));
                    simpleNode.addOpIndex(j + 1);
                    simpleNode.setSortedIndex(sorted);
                    stepList.add(simpleNode);
                }
            }

            sorted.add(array.length -1- i);

            if (!exchange) {
                //没有交换,退出循环
                break;
            }
        }

        SimpleNode simpleNode = new SimpleNode();
        simpleNode.setStepEnd(Arrays.copyOf(array, array.length));
        simpleNode.setDes("数组大小:" + array.length + " 已排序:" + array.length);
        stepList.add(simpleNode);

        return stepList;
    }


    public static List<SimpleNode> selectSortV1(int size, int range) {
        return selectSortV1(DataBuildUtils.getRandomSortArray(size, range));
    }

    public static List<SimpleNode> selectSortV1(int[] sort) {
        List<SimpleNode> stepList = new ArrayList<>();
        int length = sort.length;
        for (int i = 0; i < length - 1; i++) {
            int minIndex = i;//初始待排序的第一个元素为最小元素

            for (int j = i + 1; j < length; j++) {

                int firstOpV = sort[minIndex];
                int secondOpV = sort[j];
                boolean compareResult = firstOpV > secondOpV;


                if (compareResult) {
                    minIndex = j;//记录最小元素位置
                }

                if (j == length - 1) {
                    //每趟的最后一步-本来在循环外-处理，移到这里-便于记录step状态
                    //把最小元素移动到sort[i]
                    if (minIndex != i) { //不是本次默认下标，则交换位置

                        //exchange start
                        int tmp = sort[i];
                        sort[i] = sort[minIndex];
                        sort[minIndex] = tmp;
                        //exchange end

                        SimpleNode simpleNode = new SimpleNode();
                        simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
                        simpleNode.addOpIndex(i, minIndex);
                        simpleNode.setDes("数组大小:" + sort.length + " 已排序:" + i);
                        stepList.add(simpleNode);
                    }
                }
            }
        }

        SimpleNode simpleNode = new SimpleNode();
        simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
        stepList.add(simpleNode);
        simpleNode.setDes("数组大小:" + sort.length + " 已排序:" + sort.length);
        return stepList;
    }


    public static List<SimpleNode> insertionSort(int size, int range) {
        return insertionSort(DataBuildUtils.getRandomSortArray(size, range));
    }

    //插入排序
    public static List<SimpleNode> insertionSort(List<Integer> list) {
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i);
        }

        return insertionSort(ints);
    }

    //插入排序
    public static List<SimpleNode> insertionSort(int[] sort) {
        ZLog.d("Sort", "排序前数组:" + Arrays.toString(sort));

        List<SimpleNode> stepList = new ArrayList<>();


        int length = sort.length;

        for (int firstIndex = 1; firstIndex < length; firstIndex++) {
            //保存当前比较数字
            int key = sort[firstIndex];
            for (int secondIndex = firstIndex - 1; secondIndex >= 0; secondIndex--) {

                int firstOpV = sort[secondIndex];
                int secondOpV = key;

                boolean compareResult = firstOpV > secondOpV;

                if (compareResult) {
                    //当前位置的数字往后移一格
                    sort[secondIndex + 1] = sort[secondIndex];


                    SimpleNode stepBean = new SimpleNode();
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length)); //移动之前的数组
                    stepBean.addOpIndex(secondIndex);
                    stepBean.setDes("数组大小:" + sort.length + " 已排序:" + firstIndex);
                    stepList.add(stepBean);
                } else {
                    //本次循环结束
                    sort[secondIndex + 1] = key;


                    SimpleNode stepBean = new SimpleNode();
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    stepBean.addOpIndex(secondIndex + 1);
                    stepBean.setDes("数组大小:" + sort.length + " 已排序:" + firstIndex);

                    stepList.add(stepBean);


                    break;
                }

                if (secondIndex == 0) {
                    //本次循环结束
                    sort[0] = key;

                    SimpleNode stepBean = new SimpleNode();
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length)); //移动之前的数组
                    stepBean.addOpIndex(0);
                    stepBean.setDes("数组大小:" + sort.length + " 已排序:" + firstIndex);
                    stepList.add(stepBean);
                    break;
                }
            }
        }
        SimpleNode stepBean = new SimpleNode();
        stepBean.setStepEnd(Arrays.copyOf(sort, sort.length)); //移动之前的数组
        stepList.add(stepBean);
        stepBean.setDes("数组大小:" + sort.length + " 已排序:" + sort.length);
        return stepList;
    }


    public static List<SimpleNode> shellSortSubSet(int size, int range) {
        return shellSortSubSet(DataBuildUtils.getRandomSortArray(size, range));
    }

    public static List<SimpleNode> shellSortSubSet(int[] array) {
        List<SimpleNode> stepList = new ArrayList<>();

        int length = array.length;
        int gap = array.length;
        int i, j, k;
        do {
            // 确定分组的增量
            gap = gap / 2;
            for (i = 0; i < gap; i++) { //分组
                List<Integer> gapList = new ArrayList<>();
                gapList.add(i);
                for (j = i + gap; j < length; j += gap) {
                    gapList.add(j);
                }
                if (gap == 1) {
                    gapList.clear();
                }

                //每个分组是一个插入排序
                for (j = i + gap; j < length; j += gap) {
                    if (array[j] < array[j - gap]) {
                        int temp = array[j];
                        for (k = j - gap; k >= 0 && temp < array[k]; k -= gap) {

                            array[k + gap] = array[k];
                            SimpleNode stepBean = new SimpleNode();
                            stepBean.setStepEnd(Arrays.copyOf(array, array.length)); //移动之前的数组
                            if (gap == 1) {
                                stepBean.addOpIndex(k + gap);
                            } else {
                                stepBean.setOpIndex(gapList);
                            }
                            stepBean.setDes("数组大小:" + array.length + " 分组增量:" + gap);
                            stepList.add(stepBean);

                        }
                        array[k + gap] = temp;
                        SimpleNode stepBean = new SimpleNode();
                        stepBean.setStepEnd(Arrays.copyOf(array, array.length));
                        if (gap == 1) {
                            stepBean.addOpIndex(k + gap);
                        } else {
                            stepBean.setOpIndex(gapList);
                        }
                        stepBean.setDes("数组大小:" + array.length + " 分组增量:" + gap);
                        stepList.add(stepBean);
                    }
                }
            }
        } while (gap > 1);
        return stepList;
    }

    public static List<QuickSimpleNode> quickSort(int size, int range) {
        int[] array = DataBuildUtils.getRandomSortArray(size, range);
        List<QuickSimpleNode> stepList = new ArrayList<>();
        quickSort(stepList, array, 0, array.length - 1);
        return stepList;
    }

    //[left, right]
    private static void quickSort(List<QuickSimpleNode> stepList, int[] sort, int left, int right) {
        if (left < right) {
            //将sort[low,high]划分满足上述条件的两个子表
            int pivotPos = divide(stepList, sort, left, right);//划分
            System.out.println("pivotPos " + pivotPos);
            quickSort(stepList, sort, left, pivotPos - 1);
            quickSort(stepList, sort, pivotPos + 1, right);
        }
    }

    //划分数组使得[left,k-1]<[k]<=[k+1,right]
    private static int divide(List<QuickSimpleNode> stepList, int[] sort, int left, int right) {
        //选取第一个元素作为基准元素
        int pivot = sort[left];
        System.out.print("start " + Arrays.toString(sort) + " left:" + left + " right:" + right + " --> ");

        int firstIndex = left;
        int secondIndex = right;

        int opFirstIndex = firstIndex;
        int opSecondIndex = secondIndex;

        while (opFirstIndex < opSecondIndex) {

            while (opFirstIndex < opSecondIndex) {
                if (sort[opSecondIndex] < pivot) {
                    sort[opFirstIndex] = sort[opSecondIndex];//将比基准小的元素移到左端

                    QuickSimpleNode stepBean = new QuickSimpleNode();
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    stepBean.addOpIndex(opSecondIndex, opFirstIndex);
                    stepBean.setDes("大小:" + sort.length + " 基准数字:" + pivot);
                    stepBean.setPivot(pivot);
                    stepList.add(stepBean);
                    break;
                }
                opSecondIndex--;

                if (opFirstIndex == opSecondIndex) {
                    //基准元素归位
                    sort[opFirstIndex] = pivot;

                    QuickSimpleNode stepBean = new QuickSimpleNode();
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    stepBean.addOpIndex(opSecondIndex, opFirstIndex);
                    stepBean.setDes("大小:" + sort.length + " 基准数字:" + pivot);
                    stepBean.setPivot(pivot);
                    stepList.add(stepBean);
                }
            }


            while (opFirstIndex < opSecondIndex) {
                if (sort[opFirstIndex] > pivot) {
                    sort[opSecondIndex] = sort[opFirstIndex];//将比基准大的元素移到右端

                    QuickSimpleNode stepBean = new QuickSimpleNode();
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    stepBean.addOpIndex(opSecondIndex, opFirstIndex);
                    stepBean.setDes("大小:" + sort.length + " 基准数字:" + pivot);
                    stepBean.setPivot(pivot);
                    stepList.add(stepBean);
                    break;
                }
                opFirstIndex++;

                if (opFirstIndex == opSecondIndex) {
                    //基准元素归位
                    sort[opFirstIndex] = pivot;

                    QuickSimpleNode stepBean = new QuickSimpleNode();
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    stepBean.addOpIndex(opSecondIndex, opFirstIndex);
                    stepBean.setDes("大小:" + sort.length + " 基准数字:" + pivot);
                    stepBean.setPivot(pivot);
                    stepList.add(stepBean);
                }
            }


        }
        return opFirstIndex;
    }


    public static List<SimpleNode> mergeSortV2(int size, int range) {
        int[] array = DataBuildUtils.getRandomSortArray(size, range);
        int[] temp = new int[size];
        List<SimpleNode> stepList = new ArrayList<>();

        mergeSortV2(stepList, array, 0, array.length - 1, temp);
        return stepList;
    }


    private static void cover(int[] origin, int[] target) {
        System.arraycopy(origin, 0, target, 0, target.length);
    }

    //[start,end]
    static void mergeSortV2(List<SimpleNode> stepList, int[] sort, int start, int end, int[] temp) // start和end分别是左边界和右边界
    {
        if (start >= end) return;
        int mid = (start + end) / 2;
        mergeSortV2(stepList, sort, start, mid, temp);
        mergeSortV2(stepList, sort, mid + 1, end, temp);

        //此时 [start,mid][mid+1,end] 各自分别是有序的
        //便于计算动画,拿数据复制到temp中
        cover(sort, temp);

        // 合并两个有序序列
        int length = start; // 表示辅助空间有多少个元素
        int i_start = start;
        int i_end = mid;
        int j_start = mid + 1;
        int j_end = end;

        //两个数组合并
        while (i_start <= i_end && j_start <= j_end) {
            if (temp[i_start] < temp[j_start]) {
                sort[length] = temp[i_start];

                SimpleNode simpleNode = new SimpleNode();
                simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
                simpleNode.addOpIndex(i_start, j_start);
                simpleNode.setDes("大小:" + sort.length);
                stepList.add(simpleNode);


                length++;
                i_start++;
            } else {
                sort[length] = temp[j_start];


                SimpleNode simpleNode = new SimpleNode();
                simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
                simpleNode.addOpIndex(length, j_start);
                simpleNode.setDes("大小:" + sort.length);
                stepList.add(simpleNode);


                length++;
                j_start++;
            }
        }
        while (i_start <= i_end)  // 把剩下数的合并
        {
            sort[length] = temp[i_start];


            SimpleNode simpleNode = new SimpleNode();
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.addOpIndex(length, i_start);
            simpleNode.setDes("大小:" + sort.length);
            stepList.add(simpleNode);

            i_start++;
            length++;
        }
        while (j_start <= j_end) {
            sort[length] = temp[j_start];


            SimpleNode simpleNode = new SimpleNode();
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.addOpIndex(length, j_start);
            simpleNode.setDes("大小:" + sort.length);
            stepList.add(simpleNode);

            length++;
            j_start++;
        }
        // 把辅助空间的数据放到原空间
        //System.out.println(Arrays.toString(temp));
    }


    public static List<CountSimpleNode> countSort(int size, int range) {
        int[] array = DataBuildUtils.getRandomSortArray(size, range);
        List<CountSimpleNode> stepList = new ArrayList<>();

        countSort(stepList, array);
        return stepList;
    }


    public static int[] countSort(List<CountSimpleNode> stepList, int[] sort) {
        int[] sorted = new int[sort.length];
        int max = sort[0], min = sort[0];
        //找到最大最小值
        for (int i : sort) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }//这里k的大小是要排序的数组中，元素大小的极值差+1

        int k = max - min + 1;
        System.out.println("min:" + min);
        System.out.println("max:" + max);

        int[] c = new int[k]; //定义辅助数组
        for (int i = 0; i < sort.length; ++i) {
            c[sort[i] - min] += 1;//优化过的地方，减小了数组c的大小

            CountSimpleNode simpleNode = new CountSimpleNode(max, min);
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.setAssist(Arrays.copyOf(c, c.length));
            simpleNode.addOpIndex(i);
            simpleNode.setDes("大小:" + sort.length + " 范围:[" + min + "," + max + "]");
            stepList.add(simpleNode);
        }
        System.out.println("c start1:" + Arrays.toString(c));

        for (int i = 1; i < c.length; ++i) {
            c[i] = c[i] + c[i - 1];

            CountSimpleNode simpleNode = new CountSimpleNode(max, min);
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.setAssist(Arrays.copyOf(c, c.length));
            simpleNode.addOpIndex(i);
            simpleNode.setDes("大小:" + sort.length + " 范围:[" + min + "," + max + "]");
            stepList.add(simpleNode);
        }
        System.out.println(Arrays.toString(sort));
        System.out.println("c start2:" + Arrays.toString(c));


        for (int i = sort.length - 1; i >= 0; --i) {
            int index = (--c[sort[i] - min]);
            System.out.println(i + " " + sort[i] + " " + (sort[i] - min) + " " + (index));
            sorted[index] = sort[i];//按存取的方式取出c的元素

            sort[i] = 0;

            CountSimpleNode simpleNode = new CountSimpleNode(max, min);
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.setSortedS(Arrays.copyOf(sorted, sorted.length));
            simpleNode.setAssist(Arrays.copyOf(c, c.length));
            simpleNode.addOpIndex(index);
            simpleNode.addOpIndex(i - 1);
            simpleNode.setDes("大小:" + sort.length + " 范围:[" + min + "," + max + "]");
            stepList.add(simpleNode);
        }
        System.out.println("c end:" + Arrays.toString(c));
        return sorted;
    }

}
